package bstsetcode;

import java.util.Arrays;

/**
 * @author noob
 * @version 1.0
 * @date 2021/3/16 7:04
 * 对于merge操作的优化思路：类似于链表创建新的结点，消耗内存
 *                我们merge的时候，需要创建额外的数组；
 *
 *                优化思路就是只创建一个额外的数组，复用额外的数组
 */
public class MergeSort4 {

    public static <E extends Comparable<E>>  void sorted(E[] data){
        int left = 0;
        int right = data.length-1;


        //步骤1：创建新的数组
        E[] temp = Arrays.copyOf(data,data.length);
        mergeSorted(data,left,right,temp);
    }

    private static <E extends Comparable<E>> void mergeSorted(E[] data, int left, int right,E[] temp) {
        if(left >= right) {
            return;
        }

        int mid = (left + right )/2;

        //对arr[l,mid]进行排序
        mergeSorted(data,left,mid,temp);
        mergeSorted(data,mid+1,right,temp);
        //合并
        if(data[mid].compareTo(data[mid+1])>0){
            merge(data,left,mid,right,temp);
        }


    }

    private static <E extends Comparable<E>> void merge(E[] data, int left, int mid, int right,E[] temp) {
            //优化：不在这里开辟数组空间
//            E[] temp = Arrays.copyOfRange(data,left,right+1);


        //步骤2：额外的拷贝--把data中的left到right中的元素 都拷贝到temp中去了
        System.arraycopy(data,left,temp,left,right-left+1);

        //步骤3：还需要处理偏移量

        int i = left,j=mid+1;
        for (int k = left; k <= right; k++) {
            //判断越界的情况
            if(i > mid){ //左边数组没有数据，直接赋值有边数组的值
                data[k] = temp[j];
                j++;
            }else if( j > right){
                data[k] = temp[i];
                i++;
            }else if(temp[i].compareTo(temp[j]) <= 0){
                data[k]=temp[i];
                i++;
            }else{
                data[k]=temp[j];
                j++;
            }
        }

    }

    public static void main(String[] args) {
        int[] dataSize = {100000,1000000,10000000};
        for(int n : dataSize){
            Integer[] arr1 =ArrayGenerator.generateRandomArray(n,n);
            Integer[] copy=Arrays.copyOf(arr1,arr1.length);
            Integer[] copy2=Arrays.copyOf(arr1,arr1.length);

            SortHelper.sortTest("MergeSort",arr1);
            SortHelper.sortTest("MergeSort3",copy);
            SortHelper.sortTest("MergeSort4",copy2);
            System.out.println("---------------");
        }
    }

}
